package leetcode.editor.cn;

//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。
//
//
//
// 示例 1:
//
//
//
//
//输入：heights = [2,1,5,6,2,3]
//输出：10
//解释：最大的矩形为图中红色区域，面积为 10
//
//
// 示例 2：
//
//
//
//
//输入： heights = [2,4]
//输出： 4
//
//
//
// 提示：
//
//
// 1 <= heights.length <=10⁵
// 0 <= heights[i] <= 10⁴
//
//
// Related Topics 栈 数组 单调栈 👍 2877 👎 0

//Java：柱状图中最大的矩形
public class LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram().new Solution();
        solution.largestRectangleArea(new int[]{4,2,0,3,2,4,3,4});
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int largestRectangleArea(int[] heights) {

            int left = 0;
            int right = heights.length - 1;

            int maxArea = 0;

            while (left <= right) {

                //还需要找到 left-right之间的最小值
                int minHeight = Integer.MAX_VALUE;
                for (int i = left; i <= right; i++){
                    if(heights[i] < minHeight)
                        minHeight = heights[i];
                }

                //计算矩形面积
                int area = (right - left + 1) * minHeight;

                maxArea = Math.max(area, maxArea);
                if (heights[left] < heights[right]) {
                    left++;
                } else {
                    right--;
                }

            }


            return maxArea;


        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
